package algorithm;

import java.util.ArrayList;
import java.util.List;

public class leetcode_0332 {
    public List<String> findItinerary(List<List<String>> tickets) {
        List<List<String>> list=new ArrayList<>();
        List<List<String>> path=new ArrayList<>();
        int len=tickets.size();
        boolean [] flag=new boolean[len];
        for(int i=0;i<len;++i){
            if(tickets.get(i).get(0).equals("JFK")){
                path.add(tickets.get(i));
                flag[i]=true;
                dfs(list,path,flag,tickets,len);
                path.remove(path.size()-1);
                flag[i]=false;
            }
        }
        int index=0;
        for(int i=1;i<list.size();++i){
            for(int k=1;k<=len;++k){
                for(int j=0;j<3;++j){
                    if(list.get(i).get(k).charAt(j)<list.get(index).get(k).charAt(j)){
                        index=i;
                        k=len;
                        break;
                    }
                    else if(list.get(i).get(k).charAt(j)>list.get(index).get(k).charAt(j)){
                        k=len;
                        break;
                    }
                }
            }
        }
        return list.get(index);
    }
    public void dfs(List<List<String>> list,List<List<String>> path,boolean [] flag,List<List<String>> tickets,int len){
        if(path.size()==len){
            List<String> tem=new ArrayList<>();
            for(int i=0;i<len;++i){
                tem.add(path.get(i).get(0));
            }
            tem.add(path.get(len-1).get(1));
            list.add(tem);
        }
        for(int i=0;i<len;++i){
            if(!flag[i]&&path.get(path.size()-1).get(1).equals(tickets.get(i).get(0))){
                path.add(tickets.get(i));
                flag[i]=true;
                dfs(list,path,flag,tickets,len);
                path.remove(path.size()-1);
                flag[i]=false;
            }
        }
    }
}
